package com.yang.String_;

public class Test {
    public static void main(String[] args) {
       String haystack = "hello", needle = "ll";
    }



    public int strStr(String haystack, String needle) {
    int [] next = new int[needle.length()];
    test1(needle, next);
    int j  = -1;
    for (int i = 0; i < haystack.length(); i++) {
        while ( j>=0 && haystack.charAt(i) != needle.charAt(j)){
            j = next[j];
        }if( haystack.charAt(i) == needle.charAt(j)) {
            j++;
        }if( j == needle.length()-1){
            return i-needle.length()+1;
        }
    }
    return -1;
}



    public void test1(String s, int[] next){
        int j = -1;
        next[0] = 1;

        for (int i = 1; i < s.length(); i++) {
            while (j >= 0 && s.charAt(i) != s.charAt(j+1)){
                j = next[j];
            }if (s.charAt(i) != s.charAt(j+1)){
                j++;
            }
            next[i] = j;
        }
    }
}


